package Offer21;

import java.util.ArrayList;

/**
 * @author 23737
 * @time 2021.9.14
 * 使得数组中的元素 奇数位于偶数之前
 */
public class Test {
    public static void main(String[] args) {
        int[] exchange = new Solution().exchange(new int[]{1, 2, 3, 4});
        for (int i = 0; i < exchange.length; i++) {
            System.out.println(exchange[i]);
        }
    }
}

/*巨垃圾的一种做法，时空复杂度很高*/
class Solution {
    public int[] exchange(int[] nums) {
        if (nums.length == 0) {
            return new int[0];
        }
        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] % 2 != 0) {
                arrayList.add(0, nums[i]);
            } else {
                arrayList.add(nums[i]);
            }
        }
//        Object[] ints = arrayList.toArray();
//        Integer[] t = new Integer[arrayList.size()];
//        t = arrayList.toArray(t);
        int[] ints = new int[arrayList.size()];
        for (int i = 0; i < ints.length; i++) {
            ints[i] = arrayList.get(i);
        }
        return ints;
    }
}

/*K大佬的双指针解法*/
class SolutionTwo {
    public int[] exchange(int[] nums) {
        int i=0;
        int j = nums.length-1;
        int temp = 0;
        while(i<j){
            while(i<j && ((nums[i]&1) == 0)){
                i++;
            }
            while (i<j && ((nums[j]&1) == 1)){
                j--;
            }
            temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        return nums;
    }
}

